package classical_problems_150;

public class P_0028 {
    /*
    * next[i] 表示0-i对应的子串，其前后缀的开头有多少个字符重合
    * 这样如果第i个字符没有匹配成功，而前 i-1个字符匹配成功，则可以重新定位到next[i-1]，而不必重头开始
    * */

    private int[] get_KMP(String needle){
        int[] next = new int[needle.length()];
        next[0] = 0;
        int j = 0;
        for(int i=1; i<needle.length(); i++){
            while(j>0 && needle.charAt(j) != needle.charAt(i)){
                j = next[j-1];
            }
            if(needle.charAt(j) == needle.charAt(i)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public int strStr(String haystack, String needle) {
        if(needle.length() > haystack.length()) return -1;
        int[] next = this.get_KMP(needle);
        int j = next[0];
        int i=0;
        for(i=0; i<haystack.length() && j<needle.length(); i++){
            while(j>0 && haystack.charAt(i) != needle.charAt(j)){
                j = next[j-1];
            }
            if(haystack.charAt(i) == needle.charAt(j)){
                j++;
            }
        }
        if(j==needle.length()){
            return i-j;
        } else{
            return -1;
        }
    }

    public static void main(String[] args){
        String a="issip";
        String b="mississippi";
        P_0028 solution = new P_0028();
        System.out.println(solution.strStr(b, a));
    }
}
